package com.itheima.arithmetic.linked;

/**
 * 单链表
 */
public class MyLinkedList {

     // 头结点
     MyNode head;

     int size = 0;

     // 插入头部
     public void insertHead(int data){
        // 先构建一个节点
        MyNode newMyNode = new MyNode(data);

        // 新节点的next指向原来的head
        newMyNode.next = head;

        size ++;
    }

    // 插入链表结尾
    public void insertTail(int data){
        // 遍历链表找到尾部节点
        MyNode current = head; // 预插入位置的节点
        for (int i = 0; i < size; i++) {
            if (current.next == null) { // 最后一个节点
                break;
            }
            current = current.next;
        }
        // 先构建一个节点
        MyNode newMyNode = new MyNode(data);
        current.next = newMyNode;
        size ++;
    }

    // 中间第n个位置插入数据
    public void insertNth(int data, int position) {
        if (position == 0) { // 插入头部
            insertHead(data);
        } else {
            MyNode current = head; // 预插入位置的节点
            for (int i = 1; i < position; i++) {
                current = current.next;
            }
            // 先构建一个节点
            MyNode newMyNode = new MyNode(data);

            // 新节点的next指向current的next, 保证数据不断
            newMyNode.next = current.next;

            // 当前的点指向新加的点
            current.next = newMyNode;
        }
        size ++;
    }

    public void deletHead(){
        // 把head的下一个作为head
        head = head.next;
        size --;
    }

    /**
     * 按位置删除
     */
    public void deletNth(int position) {
         if (position == 0) { // 头部
             deletHead();
         } else {
             MyNode current = head;
             for (int i = 1; i < position; i++) {
                current = current.next;
             }

             // current 删除位置的前一个节点
             current.next = current.next.next;
         }
         size --;
    }

    /**
     * 按元素删除(Lru算法前提不能存在相同的数据)
     */
    public void delElement(int data) {

        MyNode myNode = find(data);
        if (myNode == null) {
            return; // 没有元素
        }

        MyNode current = head;
        for (int i = 0; i < size; i++) {
            if (current.value == data) {
                if (i == 0) {
                    deletHead();
                } else {
                    current.next = current.next.next;
                    size --;
                }
                break;
            }
            current = current.next;
        }
    }

    // 查找
    public MyNode find(int data){
        MyNode current = head;
        for (int i = 0; i < size; i++) {
            if (current.value == data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    // 遍历链表
    public void print() {
        MyNode current = head;
        for (int i = 0; i < size; i++) {
            System.out.println(current.value + "");
            current = current.next;
        }
    }

}


